package es.upm.gib.mappingAPI2;

import es.upm.gib.owlbasicmodel2.OWLBasicModel2;

import java.io.Serializable;
import java.util.*;

/**
 * This class represents a view of the entry of the mapping.
 * It is represented by:
 * - CustomData
 * - List of paths of the view
 * - List of bounds of the view
 * - List of identifying classes
 */
public class View implements Serializable {

    private static class Coordinates {

        private Coordinates(int x, int y) {
            this.x = x;
            this.y = y;
        }

        int x;

        int y;

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Coordinates that = (Coordinates) o;

            if (x != that.x) return false;
            if (y != that.y) return false;

            return true;
        }

        @Override
        public int hashCode() {
            int result = x;
            result = 31 * result + y;
            return result;
        }
    }


    //=======================================================================
    //ATTRIBUTES
    //=======================================================================

    private CustomData customData;

    /**
     * RDF Paths composing this view
     */
    private ArrayList<Path> paths;

    /**
     * Internal bounds among the paths of this view
     */
    private ArrayList<CoordinatesBound> bounds;

    /**
     * Identifier classes of the view
     */
    private ArrayList<Identifier> identifiers;


    //=======================================================================
    //CONSTRUCTORS
    //=======================================================================

    /**
     * Constructor: creates a new View object
     *
     * @param paths a vector of Path objects that defines the set of paths of this view
     */
    public View(ArrayList<Path> paths) {
        this.paths = paths;
        this.customData = new CustomData();
        this.bounds = new ArrayList<CoordinatesBound>();
        this.identifiers = new ArrayList<Identifier>();
    }

    /**
     * Constructor: creates a new View object
     *
     * @param paths  a vector of Path objects that defines the set of paths of this view
     * @param bounds a vector of InternalBound objects that defines the internal bounds among the paths
     */
    public View(ArrayList<Path> paths, ArrayList<CoordinatesBound> bounds) {
        this.paths = paths;
        this.bounds = bounds;
        this.customData = new CustomData();
        this.identifiers = new ArrayList<Identifier>();
    }

    View() {
        this.customData = new CustomData();
        this.bounds = new ArrayList<CoordinatesBound>();
        this.identifiers = new ArrayList<Identifier>();
        this.paths = new ArrayList<Path>();
    }

    //=======================================================================
    //PUBLIC METHODS
    //=======================================================================

    /**
     * This method returns custom data
     *
     * @return custom data
     */
    public CustomData getCustomData() {
        return customData;
    }

    /**
     * This method returns the list of bounds of the mapping
     *
     * @return list of bounds
     */
    public ArrayList<CoordinatesBound> getBounds() {
        return bounds;
    }

    /**
     * This method returns number of paths
     *
     * @return number of paths
     */
    public int getPathNumber() {
        return paths.size();
    }

    /**
     * This method returns number of bounds
     *
     * @return number of bounds
     */
    public int getBoundNumber() {
        return bounds.size();
    }

    /**
     * This method returns the path from the input position of paths
     *
     * @param index input position
     * @return path from the input position of paths
     */
    public Path getPath(int index) {
        return paths.get(index);
    }

    /**
     * This method returns the list of paths
     *
     * @return paths of the view
     */
    public ArrayList<Path> getPaths() {
        return paths;
    }

    /**
     * This method returns the internal bound from the input position
     *
     * @param index position
     * @return internal bound
     */
    public CoordinatesBound getInternalBound(int index) {
        return bounds.get(index);
    }

    /**
     * This method returns the list of internal bounds of the view
     *
     * @return list of internal bounds
     */
    public ArrayList<CoordinatesBound> getInternalBounds() {
        return bounds;
    }

    /**
     * This method set the input list of internal bounds into the view
     *
     * @param internalBounds List of internal bounds to add
     */
    public void setInternalBounds(ArrayList<CoordinatesBound> internalBounds) {
        this.bounds = internalBounds;
    }

    /**
     * This method returns the coordinates of identifiers of the view
     *
     * @return the coordinates of identifiers of the view
     */
    public ArrayList<Identifier> getIdentifiers() {
        return identifiers;
    }

    /**
     * This method adds the coordinates of the new identifier to the list
     *
     * @param id identifier class to add
     */
    public void addIdentifier(Identifier id) {
        identifiers.add(id);
    }

    /**
     * Retrieves true if the identifiers of the model contains the input identifier
     *
     * @param identifier identifier class
     * @return true if the identifiers of the model contains the input identifier, false otherwise
     */
    private boolean containID(Identifier identifier) {
        for (Identifier id : identifiers) {
            if ((id.getClass_() == identifier.getClass_()) && (id.getPath() == identifier.getPath())) {
                return true;
            } else if (isInternalBoundIdentifier(id, identifier)) {
                return true;
            }
        }
        return false;
    }

    /**
     * This method returns true if the identifier belongs to the list of identifiers of the view
     *
     * @param identifier identifier class
     * @return true if the identifier belongs to the list of identifiers of the view, false otherwise
     */
    public boolean isIdentifier(Identifier identifier) {
        if (containID(identifier)) {
            return true;
        }
        return false;
    }

    /**
     * This method determines if the input identifiers belongs to the list of bounds of the view
     *
     * @param id         first identifier
     * @param identifier second identifier
     * @return true if the input identifiers belongs to the list of bounds of the view, false otherwise
     */
    private boolean isInternalBoundIdentifier(Identifier id, Identifier identifier) {
        for (CoordinatesBound bound : bounds) {
            if ((bound.getFirstPath() == id.getPath()) && (bound.getFirstClass() == id.getClass_())) {
                if ((bound.getSecondPath() == identifier.getPath()) && (bound.getSecondClass() == identifier.getClass_())) {
                    return true;
                }
            } else if ((bound.getSecondPath() == id.getPath()) && (bound.getSecondClass() == id.getClass_())) {
                if ((bound.getFirstPath() == identifier.getPath()) && (bound.getFirstClass() == identifier.getClass_())) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * creates a normalized View.
     * <p/>
     * Given a View, the normalization process orders the paths following these criteria:
     * 1. a shorter path precedes a longer path
     * 2. if paths have the same length, the precedence is based on a lexografical order.
     * <p/>
     * The internal bounds are changed according to the changes made on the order of the paths
     *
     * @return a new normalized view
     */
    public View normalize() {
        //List<Path> ptcopy = (ArrayList<Path>) paths.clone();
        ArrayList<Path> ptcopy = new ArrayList<Path>(paths);
        int[] cor = new int[paths.size()];
        ArrayList<CoordinatesBound> bdcopy = new ArrayList<CoordinatesBound>();
        //Collections.sort(ptcopy);
        for (int i = 0; i < paths.size(); i++) {
            cor[i] = ptcopy.indexOf(paths.get(i));
        }


        if (bounds != null) {
            for (int i = 0; i < bounds.size(); i++) {
                //   System.out.println(bounds.get(i).getFirstPath()+ "->"+cor[bounds.get(i).getFirstPath()]);
                //         System.out.println(bounds.get(i).getSecondPath()+"->"+cor[bounds.get(i).getSecondPath()]);

                int tradFirst = cor[bounds.get(i).getFirstPath()];
                int tradFirstc = bounds.get(i).getFirstClass();
                int tradSecond = cor[bounds.get(i).getSecondPath()];
                int tradSecondc = bounds.get(i).getSecondClass();
                bdcopy.add(new CoordinatesBound(tradFirst, tradFirstc, tradSecond, tradSecondc));

            }


        }
        // todo normalizar el vector de internal bounds!!!
        for (CoordinatesBound internalBound : bdcopy) {
            internalBound.normalize();
        }
        bdcopy = normalizeInternalBounds(bdcopy);
        View normV = new View(ptcopy, bdcopy);
        //normV.setOrder(cor);
        return normV;
    }

    /**
     * This method normalize the list of internal bounds
     *
     * @param bdcopy list of bounds
     * @return list of bounds normalized
     */
    private ArrayList<CoordinatesBound> normalizeInternalBounds(ArrayList<CoordinatesBound> bdcopy) {
        CoordinatesBound[] sortedArray = new CoordinatesBound[0];
        sortedArray = (CoordinatesBound[]) bdcopy.toArray(sortedArray);
        Arrays.sort(sortedArray);
        return new ArrayList<CoordinatesBound>(Arrays.asList(sortedArray));
    }

    /**
     * Indicates if this View object is formed by a connected graph
     *
     * @return true if the nodes of this view form a connected graph, false otherwise
     */
    public boolean isConnected() {
        // we consider paths as the atomic elements, since a path is always a connected island
        // paths are identified by their index number, from 0 to paths.size() - 1
        // we use a depth-search algorithm, starting at path 0, using recurrence
        // we keep a relation of visited paths
        if (paths.isEmpty()) {
            return true;
        }
        Set<Integer> visitedPaths = new HashSet<>();
        visitedPaths.add(0);
        visitAllNeighborPaths(0, visitedPaths);
        return (visitedPaths.size() == paths.size());
    }

    private void visitAllNeighborPaths(int currentPath, Set<Integer> visitedPaths) {
        for (CoordinatesBound bound : getBounds()) {
            if (bound.getFirstPath() == currentPath && !visitedPaths.contains(bound.getSecondPath())) {
                visitedPaths.add(bound.getSecondPath());
                visitAllNeighborPaths(bound.getSecondPath(), visitedPaths);
            }
            if (bound.getSecondPath() == currentPath && !visitedPaths.contains(bound.getFirstPath())) {
                visitedPaths.add(bound.getFirstPath());
                visitAllNeighborPaths(bound.getFirstPath(), visitedPaths);
            }
        }
    }

    public List<String> findPathBetweenTwoClasses(int fromPath, int fromClass, int toPath, int toClass, boolean includeClasses) {
        List<String> terms = new ArrayList<>();
        List<CoordinatesBound> bounds = findBoundsBetweenTwoPaths(fromPath, toPath);
        findPathBetweenTwoClassesAux(fromPath, fromClass, toPath, toClass, includeClasses, terms, bounds);
        return terms;
    }

    public void findPathBetweenTwoClassesAux(int fromPath, int fromClass, int toPath, int toClass, boolean includeClasses, List<String> terms, List<CoordinatesBound> bounds) {
        if (!bounds.isEmpty()) {
            CoordinatesBound nextBound = bounds.remove(0);
            if (fromPath == nextBound.getFirstPath()) {
                addTermsBetweenTwoClasses(paths.get(fromPath), fromClass, nextBound.getFirstClass(), terms, includeClasses, false);
                fromPath = nextBound.getSecondPath();
                fromClass = nextBound.getSecondClass();
            } else {
                addTermsBetweenTwoClasses(paths.get(fromPath), fromClass, nextBound.getSecondClass(), terms, includeClasses, false);
                fromPath = nextBound.getFirstPath();
                fromClass = nextBound.getFirstClass();
            }
            findPathBetweenTwoClassesAux(fromPath, fromClass, toPath, toClass, includeClasses, terms, bounds);
        } else {
            // last path
            addTermsBetweenTwoClasses(paths.get(toPath), fromClass, toClass, terms, includeClasses, true);
        }
    }

    private void addTermsBetweenTwoClasses(Path path, int fromClass, int toClass, List<String> terms, boolean includeClasses, boolean includeLastElement) {
        if (fromClass < toClass) {
            // upwards
            for (int i = fromClass; i < toClass; i++) {
                Triple triple = path.get(i);
                if (includeClasses) {
                    terms.add(triple.getOrigin());
                }
                terms.add(triple.getRelation());
            }
            if (includeClasses && includeLastElement) {
                terms.add(path.get(toClass - 1).getDestination());
            }
        } else {
            // downwards
            for (int i = fromClass - 1; i >= toClass; i--) {
                Triple triple = path.get(i);
                if (includeClasses) {
                    terms.add(triple.getDestination());
                }
                terms.add(triple.getRelation());
            }
            if (includeClasses && includeLastElement) {
                terms.add(path.get(toClass).getOrigin());
            }
        }
    }

    private List<CoordinatesBound> findBoundsBetweenTwoPaths(int fromPath, int toPath) {
        List<CoordinatesBound> bounds = new ArrayList<>();
        Set<Integer> visitedPaths = new HashSet<>();
        visitedPaths.add(fromPath);
        findBoundsBetweenTwoPathsAux(fromPath, toPath, bounds, visitedPaths);
        return bounds;
    }

    private void findBoundsBetweenTwoPathsAux(int fromPath, int toPath, List<CoordinatesBound> boundsUsed, Set<Integer> visitedPaths) {
        if (fromPath != toPath) {
            for (CoordinatesBound bound : getBounds()) {
                if (!boundsUsed.contains(bound)) {
                    if (bound.getFirstPath() == fromPath && !visitedPaths.contains(bound.getSecondPath())) {
                        boundsUsed.add(bound);
                        visitedPaths.add(bound.getSecondPath());
                        findBoundsBetweenTwoPathsAux(bound.getSecondPath(), toPath, boundsUsed, visitedPaths);
                    }
                    if (bound.getSecondPath() == fromPath && !visitedPaths.contains(bound.getFirstPath())) {
                        boundsUsed.add(bound);
                        visitedPaths.add(bound.getFirstPath());
                        findBoundsBetweenTwoPathsAux(bound.getFirstPath(), toPath, boundsUsed, visitedPaths);
                    }
                }
            }
        }
    }

    /**
     * produces a String representation of the object View
     *
     * @return a String representation of the object View
     */
    public String toString() {
        return "PATHS: " + paths + ", BOUNDS: " + bounds + ", IDS" + identifiers;
    }

    /**
     * This method determines if two objects are equals
     *
     * @param obj object
     * @return true if both object are equals, false otherwise
     */
    public boolean equals(Object obj) {
        if (obj != null && obj instanceof View) {
            View v = (View) obj;


            if (v.getPathNumber() == this.getPathNumber()) {
                //  System.out.println("ENTER IN EQUALIZATION");
                View comp1 = this.normalize();
                View comp2 = v.normalize();
                // System.out.println("COMPARE:\n"+comp1+"\n"+comp2+"\n result:"+comp1.paths.equals(comp2.paths)+comp1.bounds.equals(comp2.bounds));

                if (comp1.paths.equals(comp2.paths) && comp1.bounds.equals(comp2.bounds) && comp1.customData.equals(comp2.customData) && comp1.identifiers.equals(comp2.identifiers)) {
                    return true;
                }
            }
            return false;
        }
        return false;
    }

    @Override
    public int hashCode() {
        // first normalize, then calculate hash
        View normalizedView = normalize();
        return normalizedView.paths.hashCode();
    }

    /**
     * returns the number of paths in this view
     *
     * @return the number of paths in this view
     */
    public int size() {
        return paths.size();
    }

    /**
     * Checks if the view is subsumed in the one given as parameter
     *
     * @param compareView the view to compare with
     * @param model       the RDF model to which the given view conforms
     * @return true if this View is subsumed in compareView
     */
    public boolean isSubsumed(View compareView, OWLBasicModel2 model) {
        //Both of the views are normalized to make the comparison easier.
        //Checks path by path for a match. In case of not finding one, a
        //false value is returned meaning "is not subsumed"


        if (compareView == null || model == null)
            return false;

        View alpha = this.normalize(this, model);
        View beta = compareView.normalize(compareView, model);

        if (alpha.size() != beta.size())
            return false;

        ArrayList<String> parents = new ArrayList<String>();
        for (Path alphaPath : alpha.paths) {
            for (Path betaPath : beta.paths) {
                //comparing Origins
                String alphaOrigin = alphaPath.firstElement().getOrigin();
                String betaOrigin = betaPath.firstElement().getOrigin();
                parents = new ArrayList<String>();
                model.ascendantHierarchyClass(alphaOrigin, parents);
                //comparing Destinations
                if (parents.contains(betaOrigin)) {
                    String alphaDestination = alphaPath.firstElement().getDestination();
                    String betaDestination = betaPath.firstElement().getDestination();
                    parents = new ArrayList<String>();
                    model.ascendantHierarchyClass(alphaDestination, parents);
                    if (parents.contains(betaDestination)) {
                        //comparing Relations
                        String alphaRelation = alphaPath.firstElement().getRelation();
                        String betaRelation = betaPath.firstElement().getRelation();
                        parents = new ArrayList<String>();
                        model.ascendantHierarchyProperty(alphaRelation, parents);
                        if (parents.contains(betaRelation)) {
                            beta.paths.remove(betaPath);
                            break;
                        }
                    }
                }
                //Case of reaching last path means that no match have been found.
                if (beta.paths.size() == beta.paths.indexOf(betaPath) + 1)
                    return false;
            }
        }
        return true;
    }

    /**
     * Normalization of a view. An associated RDF model allows considering inverse properties in the normalization process
     *
     * @param view  the view to normalize
     * @param model the RDF model to which the given view conforms (null indicates that no model is used)
     * @return a normalized version of the given view. The returned view is semantically identical to the received one
     */
    public static View normalize(View view, OWLBasicModel2 model) {
        // The normalization process has three steps:
        // 1) decomposition of paths in atomic paths
        // 2) searching of inverse relations (if model is available)
        // 3) sorting of resulting paths and coordinate bounds
        //
        // For this process, the information from the view used is: a) the paths, b) the bounds and c) the identifier information
        //

        // the resulting normalized view
        View normView = new View();

        // 1) decomposition in atomic paths
        // transfer the paths from the old view to the normalized view. This is done path by path
        Map<Coordinates, Coordinates> coordinatesMap = new HashMap<Coordinates, Coordinates>();
        Set<CoordinatesBound> newCoordinatesBound = new HashSet<CoordinatesBound>();
        for (int i = 0; i < view.paths.size(); i++) {
            Path path = view.paths.get(i);
            normView.paths.addAll(decomposePath(path, i, coordinatesMap, normView.paths.size(), newCoordinatesBound));
        }

        // transfer old coordinates bounds to the new normalized view
        for (CoordinatesBound coordinatesBound : view.bounds) {
            Coordinates newFirst = coordinatesMap.get(new Coordinates(coordinatesBound.getFirstPath(), coordinatesBound.getFirstClass()));
            Coordinates newSecond = coordinatesMap.get(new Coordinates(coordinatesBound.getSecondPath(), coordinatesBound.getSecondClass()));
            newCoordinatesBound.add(new CoordinatesBound(newFirst.x, newFirst.y, newSecond.x, newSecond.y));
        }
        normView.bounds.addAll(newCoordinatesBound);

        // transfer the old identifiers
        for (Identifier identifier : view.identifiers) {
            Coordinates newIdentifier = coordinatesMap.get(new Coordinates(identifier.getPath(), identifier.getClass_()));
            normView.addIdentifier(new Identifier(newIdentifier.x, newIdentifier.y));
        }

        // 2) searching of inverse relations (if model is available)
        if (model != null) {
            ArrayList<String> inverses;
            String property;
            for (int i = 0; i < normView.paths.size(); i++) {
                Path path = normView.getPath(i);
                property = model.completeName(path.get(0).getRelation());
                inverses = model.getObjectPropertyInverses(property);
                //Case of having inverse
                if (!inverses.isEmpty()) {
                    //Case of having inverse and being lower alphabetically
                    if (property.compareToIgnoreCase(Collections.min(inverses)) > 0) {
                        path.removeElementAt(0);
                        property = Collections.min(inverses);
                        path.add(new Triple(model.getDomainForObjectProperty(property).get(0), property, model.getRangeForObjectProperty(property).get(0)));

                        Coordinate oldFirst = new Coordinate(i, 0);
                        Coordinate oldSecond = new Coordinate(i, 1);


                        for (int j = 0; j < normView.bounds.size(); j++) {
                            //Update CoordinatesBound to match the new paths
                            CoordinatesBound bound = normView.bounds.get(j);
                            if (bound.getFirstPath() == oldFirst.getPath() && bound.getFirstClass() == oldFirst.getClass_()) {
                                normView.bounds.set(j, new CoordinatesBound(oldSecond.getPath(), oldSecond.getClass_(), bound.getSecondPath(), bound.getSecondClass()));
                            }
                            if (bound.getFirstPath() == oldSecond.getPath() && bound.getFirstClass() == oldSecond.getClass_()) {
                                normView.bounds.set(j, new CoordinatesBound(oldFirst.getPath(), oldFirst.getClass_(), bound.getSecondPath(), bound.getSecondClass()));
                            }
                            if (bound.getSecondPath() == oldFirst.getPath() && bound.getSecondClass() == oldFirst.getClass_()) {
                                normView.bounds.set(j, new CoordinatesBound(bound.getFirstPath(), bound.getFirstClass(), oldSecond.getPath(), oldSecond.getClass_()));
                            }
                            if (bound.getSecondPath() == oldSecond.getPath() && bound.getSecondClass() == oldSecond.getClass_()) {
                                normView.bounds.set(j, new CoordinatesBound(bound.getFirstPath(), bound.getFirstClass(), oldFirst.getPath(), oldFirst.getClass_()));
                            }
                        }

                        if (normView.identifiers.contains(oldFirst))
                            normView.identifiers.set(normView.identifiers.indexOf(oldFirst), new Identifier(oldSecond.getPath(), oldSecond.getClass_()));
                        if (normView.identifiers.contains(oldSecond))
                            normView.identifiers.set(normView.identifiers.indexOf(oldSecond), new Identifier(oldFirst.getPath(), oldFirst.getClass_()));
                    }
                }
            }
        }


        // 3) sorting of resulting paths and coordinate bounds
        for (int i = 0; i < normView.paths.size(); i++) {
            for (int j = i + 1; j < normView.paths.size(); j++) {
                if (pathIsGreater(normView.paths.get(i), normView.paths.get(j))) {
                    switchPaths(normView, i, j);
                }
            }
        }

        //Bound Sorting and Fixing (3 steps)
        //1st Step
        //Fixes bounds by changing coordinates if needed
        ArrayList<CoordinatesBound> newBounds = (ArrayList<CoordinatesBound>) normView.bounds.clone();
        int i = 0;
        int j = 0;
        while (!newBounds.isEmpty()) {
            LinkedList<Coordinate> checkCoords = new LinkedList<Coordinate>();
            checkCoords.add(new Coordinate(i, j));
            while (!checkCoords.isEmpty()) {
                Coordinate cCoord = checkCoords.pollFirst();
                int k = 0;
                while (k < newBounds.size()) {
                    CoordinatesBound bound = newBounds.get(k);
                    if (bound.getFirstPath() == cCoord.getPath() && bound.getFirstClass() == cCoord.getClass_()) {
                        if (cCoord.getPath() != i || cCoord.getClass_() != j) {
                            int index = normView.bounds.indexOf(bound);
                            normView.bounds.set(index, new CoordinatesBound(i, j, bound.getSecondPath(), bound.getSecondClass()));
                        }
                        checkCoords.add(new Coordinate(bound.getSecondPath(), bound.getSecondClass()));
                        newBounds.remove(bound);
                    } else if (bound.getSecondPath() == cCoord.getPath() && bound.getSecondClass() == cCoord.getClass_()) {
                        if (cCoord.getPath() != i || cCoord.getClass_() != j) {
                            int index = normView.bounds.indexOf(bound);
                            normView.bounds.set(index, new CoordinatesBound(bound.getFirstPath(), bound.getFirstClass(), i, j));
                        }
                        checkCoords.add(new Coordinate(bound.getFirstPath(), bound.getFirstClass()));
                        newBounds.remove(bound);
                    } else {
                        k++;
                    }
                }
            }
            if (j == 1) {
                j = 0;
                i++;
            } else {
                j++;
            }
        }

        //2nd Step
        //Switching of bounds if first coordinates as greater than the second ones
        for (CoordinatesBound bound : normView.bounds) {
            if (bound.getFirstPath() > bound.getSecondPath()) {
                int index = normView.bounds.indexOf(bound);
                normView.bounds.set(index, new CoordinatesBound(bound.getSecondPath(), bound.getSecondClass(), bound.getFirstPath(), bound.getFirstClass()));
                bound = new CoordinatesBound(bound.getSecondPath(), bound.getSecondClass(), bound.getFirstPath(), bound.getFirstClass());
            }
            //Fixing identifiers
            for (Identifier ident : normView.identifiers) {
                if (ident.getPath() == bound.getSecondPath() && ident.getClass_() == bound.getSecondClass()) {
                    normView.identifiers.set(normView.identifiers.indexOf(ident), new Identifier(bound.getFirstPath(), bound.getFirstClass()));
                }
            }
        }

        //3rd Step
        //Sorting bounds. First coordinates ascendant and the second coordinates ascendant
        for (i = 0; i < normView.bounds.size(); i++) {
            for (j = i + 1; j < normView.bounds.size(); j++) {
                if (
                        (normView.bounds.get(i).getFirstPath() > normView.bounds.get(j).getFirstPath())
                                ||
                                (normView.bounds.get(i).getFirstPath() == normView.bounds.get(j).getFirstPath()
                                        &&
                                        normView.bounds.get(i).getSecondPath() > normView.bounds.get(j).getSecondPath())

                        ) {
                    CoordinatesBound aux = normView.bounds.get(i);
                    normView.bounds.set(i, normView.bounds.get(j));
                    normView.bounds.set(j, aux);
                }
            }
        }

        return normView;
    }


    private static void switchPaths(View normView, int i, int j) {
        Path tempPath = normView.paths.get(i);
        normView.paths.set(i, normView.paths.get(j));
        normView.paths.set(j, tempPath);
        for (int k = 0; k < normView.bounds.size(); k++) {
            CoordinatesBound coordinatesBound = normView.bounds.get(k);
            if (coordinatesBound.getFirstPath() == i) {
                normView.bounds.set(k, new CoordinatesBound(j, coordinatesBound.getFirstClass(), coordinatesBound.getSecondPath(), coordinatesBound.getSecondClass()));
                coordinatesBound = normView.bounds.get(k);
            } else if (coordinatesBound.getFirstPath() == j) {
                normView.bounds.set(k, new CoordinatesBound(i, coordinatesBound.getFirstClass(), coordinatesBound.getSecondPath(), coordinatesBound.getSecondClass()));
                coordinatesBound = normView.bounds.get(k);
            }
            if (coordinatesBound.getSecondPath() == i) {
                normView.bounds.set(k, new CoordinatesBound(coordinatesBound.getFirstPath(), coordinatesBound.getFirstClass(), j, coordinatesBound.getSecondClass()));
            } else if (coordinatesBound.getSecondPath() == j) {
                normView.bounds.set(k, new CoordinatesBound(coordinatesBound.getFirstPath(), coordinatesBound.getFirstClass(), i, coordinatesBound.getSecondClass()));
            }
        }
        for (int k = 0; k < normView.identifiers.size(); k++) {
            Identifier identifier = normView.identifiers.get(k);
            if (identifier.getPath() == i) {
                normView.identifiers.set(k, new Identifier(j, identifier.getClass_()));
            } else if (identifier.getPath() == j) {
                normView.identifiers.set(k, new Identifier(i, identifier.getClass_()));
            }
        }
    }

    private static boolean pathIsGreater(Path path1, Path path2) {
        StringBuilder str1 = buildPathString(path1);
        StringBuilder str2 = buildPathString(path2);
        return str1.toString().compareTo(str2.toString()) > 0;
    }

    private static StringBuilder buildPathString(Path path) {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < path.size(); i++) {
            Triple triple = path.getPath().get(i);
            if (i == 0) {
                stringBuilder.append(triple.getOrigin());
            }
            stringBuilder.append(triple.getRelation());
            stringBuilder.append(triple.getDestination());
        }
        return stringBuilder;
    }

    private static Collection<Path> decomposePath(Path path, int pathCount, Map<Coordinates, Coordinates> coordinatesMap, int normPathCount, Set<CoordinatesBound> newCoordinatesBound) {
        // each triple of the path forms a new atomic path
        Collection<Path> paths = new ArrayList<Path>();
        for (int i = 0; i < path.getPath().size(); i++) {
            Triple triple = path.getPath().get(i);
            paths.add(new Path(triple));
            coordinatesMap.put(new Coordinates(pathCount, i), new Coordinates(normPathCount, 0));
            if (i == path.getPath().size() - 1) {
                // the last triple adds an additional coordinate map
                coordinatesMap.put(new Coordinates(pathCount, path.getPath().size()), new Coordinates(normPathCount, 1));
            }
            if (i > 0) {
                // create bound with previous triple
                newCoordinatesBound.add(new CoordinatesBound(normPathCount - 1, 1, normPathCount, 0));
            }
            normPathCount++;
        }
        return paths;
    }

}
